// Threaded Sieve of Eratosthenes
// William A. Katsak
// Provided as an example for Rutgers CS 416, Section 1
// Compile with: gcc sieve_threaded.c -o sieve_threaded -pthread -lm

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <time.h>
#include <unistd.h>
#include <math.h>

#define DEBUG 0

void *worker_thread(void *thread_args);

typedef struct thread_data_t
{
	int thread_num;
	int start_index;
	int end_index;
	
} thread_data_t;

short *array;
pthread_t *thread;
thread_data_t *thread_info;

int TARGET_PRIMES;
int NUM_THREADS;
int DISPLAY_PRIMES;

//pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
//pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
//int cond_count = 0;

pthread_barrier_t barrier;
pthread_barrier_t barrier2;

// Set up the clock stuff.
struct timeval start_time[1];
struct timeval finish_time[1];
unsigned long diff = 0;

// Shared data for the threads.
long last_prime = 2;

// Main function (program entry point).
int main (int argc, const char * argv[])
{
  // Check for a minimum argument count of 3. If not, output a help message.
  if(argc < 3)
  {
    printf("Usage: %s TARGET_PRIMES NUM_THREADS [DISPLAY_PRIMES]\n", argv[0]);
    return 0;
  }

  // Otherwise convert the argument strings into integers.
  TARGET_PRIMES = atoi(argv[1]);
  NUM_THREADS = atoi(argv[2]);

  // If we have a fourth argument, use it for the DISPLAY_PRIMES flag.
  if(argc == 4)
    DISPLAY_PRIMES = atoi(argv[3]);
  else
    DISPLAY_PRIMES = 0;

	// Create an array and thread descriptors.
  array = malloc(sizeof(short) * (TARGET_PRIMES+2));
  thread = malloc(sizeof(pthread_t) * NUM_THREADS);
  thread_info = malloc(sizeof(thread_data_t) * NUM_THREADS);
  
  // Declare an iterator.
	unsigned long i;

	// Populate the array with trues.
	for(i=2; i<=TARGET_PRIMES; i++)
	{
		array[i] = 1;
	}

	// Take a timestamp.
	gettimeofday(start_time, NULL);
	
	// Set up the barrier for synchronization.
	pthread_barrier_init(&barrier, NULL, NUM_THREADS+1);
  pthread_barrier_init(&barrier2, NULL, NUM_THREADS+1);
	
  // Figure out the split of the array between the threads.
	int start = 2;
	int split = (TARGET_PRIMES-2)/NUM_THREADS;
	
	// Create the threads.
	for(i=0; i<NUM_THREADS; i++)
	{
    // Split up the work that needs to be done.
    // e.g. which regions of the array each thread is responsible for/
		thread_info[i].start_index = start;
		thread_info[i].end_index = start + split;
		start += split+1;
		if(i==NUM_THREADS-1) thread_info[i].end_index = TARGET_PRIMES;

    // Assign each thread a unique id.
		thread_info[i].thread_num = i;

    // Actually create each thread.
		pthread_create(&thread[i], NULL, worker_thread, &thread_info[i]);		

   // Output the thread details.
    printf("Thread %i created range %i-%i...\n", thread_info[i].thread_num, thread_info[i].start_index, thread_info[i].end_index);
	}

  // Main algorithm and thread synchronization.
	while(1)
	{
		DEBUG && printf("Main loop:\n");

    // Wait on a barrier. This synchronizes the worker threads and the main thread.
    // We can't pass this point until all of the worker threads have STARTED their cycles.
    pthread_barrier_wait(&barrier);

    // If we are on the last cycle, break out of the loop.
		if(last_prime > sqrt(TARGET_PRIMES))
			break;
	
// This code does the same thing as the second barrier.
	
/*  // Use a condition variable to make sure that all of the workers have finished
    // this cycle before continuing.
		pthread_mutex_lock(&mutex);s
		if(cond_count < NUM_THREADS)
			pthread_cond_wait(&cond, &mutex);
		pthread_mutex_unlock(&mutex);

		DEBUG && printf("Got past condition variable, cond_count %i\n", cond_count);
*/
    // Wait on another barrier. This one is used to synchronize when the threads all FINISH.
    pthread_barrier_wait(&barrier2);

    // Find the next true cell (should be the next prime).
		while(array[++last_prime] == 0);
			
		DEBUG && printf("New prime: %lu\n", last_prime);

// Part of the conditional variable based barrier that we aren't using.	
  	/*
    // Reset the conditional variable count.
		pthread_mutex_lock(&mutex);
		cond_count = 0;
		pthread_mutex_unlock(&mutex);
			*/	
		DEBUG && printf("Finished main loop\n");
	}
	
	DEBUG && printf("Ended main loop, joining threads...\n");
	
	// Join the threads.
	for(i=0; i<NUM_THREADS; i++)
	{
		pthread_join(thread[i], NULL);
	}
	
  // Get the finishing timestamp.
	gettimeofday(finish_time, NULL);
	diff = (finish_time->tv_sec - start_time->tv_sec) * 1000000 + (finish_time->tv_usec - start_time->tv_usec);
	printf("Time %lu\n", diff);
	
	
	// Print primes.
	for(i=2; i<=TARGET_PRIMES && DISPLAY_PRIMES; i++)
	{
		if(array[i] == 1)
		{
			printf("%lu ", i);
		}
	}

  // Output a single newline at the end of the program.
  printf("\n");

  // Return 0.	
  return 0;
}

void *worker_thread(void *thread_args)
{
  // Get the data out of the argument struct.
	int thread_num = ((thread_data_t*)thread_args)->thread_num;
	int start_index = ((thread_data_t*)thread_args)->start_index;
	int end_index = ((thread_data_t*)thread_args)->end_index;
	
	while(1)
	{
		DEBUG && printf("Thread %i waiting on barrier...prime: %lu\n", thread_num, last_prime);

    // Wait on the first barrier.		
    pthread_barrier_wait(&barrier);

    // If we are done, end the thread.
		if(last_prime > sqrt(TARGET_PRIMES))
			pthread_exit(NULL);

    // Find the spot to start crossing numbers off.
		unsigned long j;
		for(j=start_index; ((j%last_prime != 0) && j <= TARGET_PRIMES) || j==last_prime; j++);
			
		DEBUG && printf("Thread %i, aligned to %lu...\n", thread_num, j);
		
    // Cross off the numbers.
		for(j; j<=end_index; j+=last_prime)
		{
			array[j] = 0;
		}

    // Our other condition variable based barrier.
		/*
    // Signal the condition variable that we finished.	
		pthread_mutex_lock(&mutex);
		cond_count++;
		if(cond_count == NUM_THREADS)
			pthread_cond_signal(&cond);
		pthread_mutex_unlock(&mutex);
		*/

    // Wait on our ending barrier.
    pthread_barrier_wait(&barrier2);

		DEBUG && printf("Thread %i done, finished cycle...\n", thread_num);
	}

	DEBUG && printf("FINISHED THREAD...\n");
  // Exit the thread. We shouldn't ever really get this far.
	pthread_exit(NULL);
}

